This invention relates to an adaptive filter which is a type of digital filter used for noise canceling, system modeling, among other applications, and to a method of renewing its coefficients for each new set of input data samples.
A variety of algorithms have been devised and used for adaptive data processing. Examples are the least mean square (LMS) algorithm and the recursive least square (RLS) algorithm. The LMS algorithm in particular has been used most extensively by virtue of a smaller amount of computations required, simplicity of circuitry, and ease of implementation, even though it is poorer in convergence than the other algorithms.
FIG. 1 of the attached drawings shows a prior art adaptive digital filter based on the LMS algorithm. It has an input terminal 10 for receiving input data samples x(k) at constant sampling intervals. The input terminal 10 is connected to a series of L (integer of more than one) delay elements M.sub.1, M.sub.2, . . . M.sub.L which successively impart a unit delay of one sampling interval to the input data samples x(k). Accordingly, (L+1) input data samples x(k), x(k-1), x(k-2), . . . x(k-L) of different sampling intervals are obtained concurrently on (L+1) lines C.sub.0 -C.sub.L, respectively, which are connected respectively to the input terminal 10 and to the outputs of the delay elements M.sub.1 -M.sub.l. Multipliers A.sub.0, A.sub.1, . . . A.sub.L multiply the input data samples x(k)-x(k-L) by respective coefficients w.sub.0 (k), w.sub.1 (k), . . . w.sub.L (k), thereby producing outputs x(k)w.sub.0 (k), x(k-1)w.sub.1 (k), . . . x(k-L)w.sub.L (k). These outputs x(k)w.sub.0 (k)-x(k-L)w.sub.L (k) are all directed into an adder 12 thereby to be added together into an output y(k). This output y(k) is then applied to a difference detector 14, which produces a difference signal e(k) representative of the difference between the adder output y(k) and a reference signal d(k).
The adder output y(k) and the difference detector output e(k) can be expressed as: EQU y(k)=w.sub.0 (k)x(k)+w.sub.1 (k)x(k-1) . . . +w.sub.L (k)x(k-L)(1) EQU e(k)=d(k)-y(k). (2).
In adaptive digital filters in general, the coefficients w.sub.0 (k)-w.sub.L (k) are renewed for each sampling interval as by a digital signal processor. Each set of input data samples x(k)-x(k-L) on the lines C.sub.0 -C.sub.L are multiplied by each renewed set of coefficients. New coefficients at discrete time k are obtained by the equation: EQU wi(k)=wi(k-1)+2 .mu.e(k-1)x(k-1) (3)
where
k-1=discrete time of the sampling interval preceding that of the time k PA1 i=variable indicating the 0'th to L'th of the lines C.sub.0 -C.sub.L PA1 wi(k-1)=coefficients of the preceding sampling interval PA1 e(k-1)=difference signal of the preceding sampling interval PA1 x(k-1)=input data of the preceding sampling interval PA1 .mu.=constant called stepsize. PA1 .lambda..sub.max =maximum of the eigenvalues of the correlation matrix of the input data x(k). PA1 T.sub.ij =elements of an interconnection matrix representing the strengths of connections PA1 I.sub.i =bias input of each neuron i. PA1 i and j=variable denoting the digits from 0'th to L'th PA1 T.sub.ij (k)=(L+1).sup.2 values used in renewal computation of the coefficients PA1 I.sub.i (k)=(L+1) values used in renewal computation of the coefficients PA1 x(k-i)=(L+1) data samples selected successively from the concurrently obtained (L+1) samples PA1 x(k-j)=(L+1) data samples selected successively from the concurrently obtained (L+1) samples; PA1 w.sub.i n(k)=values of the (L+1) coefficients after being renewed at each of the n renewals PA1 w.sub.j n-1(k)=(L+1) coefficients before being renewed;
The stepsize constant is defined by the formula: EQU 0&lt;.mu.&lt;1/.lambda..sub.max ( 4)
where
Theoretically, the stepsize .mu. should be as great as possible purely for the purpose of speeding the convergence of the LMS algorithm. However, actually, the stepsize has the upper limit determined by the formula (4) above. Too great a value of the stepsize is also undesirable from the standpoint of system stability.
A solution to this problem is found in the article entitled "Performance Improvement of LMS Algorithm" by Takahashi in pp. 19-24 of the Vol. 74-A, No. 1 issue of The Transactions of the Institute of Electronics, Information and Communication Engineers published Jan. 25, 1991, by the Institute of Electronics, Information and Communication Engineers of Tokyo, Japan. Essentially, Takahashi teaches a coefficient renewal method that does not rely on the difference signal e(k) but which is based upon the similarity between LMS and the Hopfield neural network model. For more details on neutral networks, reference may be had to the article entitled "Neural Networks for Computation: Number Representations and Programming Complexity" by Takeda et al. in the Volume 25, Number 18 issue of Applied Optics published by the Optical Society of America.
The Hopfield neural network model is shown in FIG. 2 in order to make clear its relationship with the present invention. The Hopfield model consists of a multiplicity of mutually interconnected nonlinear devices called neurons. The states of these neurons are characterized by their outputs that take binary values 0 and 1. The dynamics of neurons in the Hopfield model can be described in both discrete and continuous spaces. The strengths of interconnections between neurons are symmetrical. Input U.sub.i to each neuron i is defined as: ##EQU1## where N=number of neurons
The output V.sub.i of each neuron i is renewed as follows in the discrete model: ##EQU2##
If the strengths T.sub.ij of interconnections are symmetrical, that is, if T.sub.ij =T.sub.ji, then the network energy E expressed by the following equation will reduce to a minimum with the network operation: ##EQU3##
In order to associate the Hopfield model with the prior art adaptive filter of FIG. 1, the output of each neuron at the time k may be expressed as the sum of the function g[U.sub.i (k)] and the neuron output V.sub.i (k-1) at the time (k-1): ##EQU4##
The function (g) is defined as follows for correspondence with the LMS algorithm: ##EQU5##
The thus defined network energy can be expressed by the following equation, which is the same as Equation (7): ##EQU6##
The network energy as defined by Equation (10) changes as follows when the output of each neuron i changes from V.sub.i (k-1) to V.sub.i (k) from time (k-1) to time k: ##EQU7##
From the relations of Equation (9), the change of the network energy is always negative, with the energy decreasing with network operation. The square of the difference signal e(k) may be used as follows in order to apply the model of Equation (8) to the prior art adaptive filter of FIG. 1: ##EQU8##
The energy E in Equation (12) is the quadratic function of the coefficients of the prior art adaptive filter at the time k and has a single minimum value. The output V in Equation (10) correspond to the coefficients w in Equation (12), and T.sub.ij and I.sub.i in Equation (10) correspond respectively to -2x(k-i)x(k-j) and 2d(k)x(k-i). Let the former be T.sub.ij (k) and the latter I.sub.i (k). Then ##EQU9##
The term d.sup.2 (k) in Equation (12) is constant and so negligible.
In the Takahashi article cited above, T.sub.ij (k) and I.sub.i (k) are computed to renew the coefficients W.sub.0 (k)-W.sub.L (k) of the prior art FIG. 1 adaptive filter. More specifically, Takahashi teaches a coefficient renewal method for an adaptive digital filter of the kind comprising: (a) means for supplying a reference signal k(k) at predetermined sampling times; (b) means for supplying samples of input data, associated with the reference signal, at the predetermined sampling times; and (c) data processing means for concurrently providing (L+1) input data samples, from 0'th to L'th, by successively imparting a unit delay of one predetermined sampling interval to the input data samples, for multiplying the 0'th to L'th input data samples by 0'th to L'th coefficients w.sub.0 (k), w.sub.1 (k), . . . w.sub.L (k), respectively, and for adding all the multiplied data samples into an output y(k).
Takahashi's method comprises the steps of: (a) computing, from the (L+1) input data samples and the reference signal at any one sampling time k: EQU T.sub.ij (k)=-2x(k-i)x(k-j) EQU I.sub.i (k)=2d(k)x(k-i)
where
(b) renewing, on the bases of the above computed T.sub.ij (k) and I.sub.i (k) and the coefficients w.sub.0 (k)-w.sub.L (k) at the sampling time k, the coefficients n times, where n is an integer of at least two, during a time interval from the sampling time k to the next sampling time (k+1) according to the equation: ##EQU10## where w.sub.i n-1=values of the (L+1) coefficients before being renewed at each of the n renewals
and (c) using the values of the coefficients obtained at the n'th renewal as the coefficients for the next sampling time (k+1).
The range of values of the stepsize constant for the convergence of Takahashi's modified LMS algorithm is the same as that for the conventional LMS algorithm, set forth in Equation (4). However, since Takahashi method teaches n renewals of the coefficients during each sampling interval, the time constant is 1/4 .mu.n.lambda. which is 1/n of the time constant, 1/4 .mu..lambda., of the conventional LMS algorithm. This advantage has been offset, however, by a relatively large amount of computations required for coefficient renewal.